The present invention is directed to channel access methods that provide Quality of Service (“QoS”) for shared communications, more specifically to channel access methods that provide Quality of Service on IEEE 802.11 wireless networks.
The abbreviations and acronyms used in this application are well known to those skilled in the art and can be readily located in the IEEE 802.11 standard, or in the IEEE 802.11E QoS baseline proposal. See Michael Fischer, QoS Baseline Proposal, IEEE 802.11 Standards Committee, Document IEEE 802.11-00/360 (Nov. 7, 2000); also QoS Baseline Proposal Revision 1, Document IEEE 802.11-00/360R1 (Nov. 7, 2000) and QoS Baseline Proposal Revision 2, Document IEEE 802.11-00/360R2 (Nov. 9, 2000), the contents of which are hereby incorporated by reference. Some of the abbreviations and acronyms used in this application are:
ACKAcknowledgement;APAccess Point;BSSBasic Service Set;BSSIDBasic Service Set Identification;CCAClear Channel Assessment;CFPContention-Free Period;CF-PollableContention-free PollableCPContention Period;CWContention Window;DCFDistributed Coordination Function;DIFSDistributed (coordination function) Interframe Space;CWContention Window;DTIMDelivery Traffic Indication Message;EAPEnhanced Access Point;IFSInterframe Space;MACMedium Access ControlNAVNetwork Allocation Vector;PCFPoint Coordination Function;P-CFBPoint-controlled Contention-free Bursts;PIFSPoint (coordination function) Interframe Space;QoSQuality of Service;SBMSubnet Bandwidth Manager;SIFSShort Interframe Space;STAStation;V-DCFVirtual Distributed Coordination Function;WSTAWireless (enhanced) Station.
In the description that follows, an “outbound” transmission is a transmission from an AP and an “inbound” tansmission is directed to an AP.
The IEEE 802.11E QoS working group has adopted a baseline proposal (hereinafter “baseline proposal”) for channel access methods that provide QoS on 802.11 wireless LANs. The baseline proposal defines three QoS levels—a “prioritised” DCF-based solution and “prioritised” and “parameterised” PCF-based solutions. It is generally agreed that a single unified approach is better from a user perspective; however, no single approach, as it is currently defined, is applicable to all environments. A PCF approach is more deterministic and efficient in single-BSS environments; however, it is difficult to implement a CFP scheduling algorithm in environments with BSS overlap. The present invention is directed to an integrated DCF/PCF channel access model that uses V-DCF for lightly and moderately loaded channels, and dynamically uses unscheduled “Point-controlled Contention-free Bursts”, to arbitrate channel contention, as the network load increases.
The baseline “prioritised” solutions are intended for stations that simply send and receive prioritised frames. The baseline “parameterised” solution is intended for WSTAs that use a signaling protocol to establish bandwidth requirements and delay constraints. This invention, the Point-controlled Contention Arbitration model, or PCCA model, requires all WSTAs to implement sufficient channel access and interface functions to support optional parameterised services. QoS features can be added to an AP implementation on an incremental basis.
The baseline proposal discloses a virtual DCF protocol (“V-DCF”). By design, the V-DCF, or level 1 in the baseline proposal, cannot provide integrated services such as “Controlled Load” and “Guaranteed Bandwidth”. Two fundamental requirements are lacking for controlled load service. 1) The total traffic at a given QoS priority must be limited (i.e. by admission control), and 2) higher priority traffic cannot be affected by lower priority traffic. The V-DCF level cannot support admission control because it lacks even a simple signaling protocol. The V-DCF access method, with contention offset and CWmin values per category, only statistically increases the probability of channel access for higher-priority packets. A tiered channel access method can be used to isolate a high-priority traffic category but only if the idle sense time, required for any lower-priority traffic category, is greater than the sum of the idle sense time plus the maximum CW value for the high-priority category. However, the tiered method doesn't scale well for large high-priority populations. “Guaranteed Bandwidth” service has the same requirements as controlled load and also requires a deterministic channel access method.
Presently, 802.11 networks use two protocols, the DCF and PCF. The DCF works great under low load situations. The PCF works optimal under high load conditions. The DCF works better in networks were BSSs overlap, the PCF is ideally suited for networks were BSSs are carefully planned not to overlap. The DCF has a relatively low implementation complexity, the PCF is reputed to be more complex to implement. The DCF does not allow explicit access control, the PCF does. The DCF efficiency drops considerably in densely populated BSSs, the PCF has no scaling problem.
Due to the inability of the PCF to work well under overlapping BSS conditions and the high implementation complexity, the PCF has not yet been widely adopted in current 802.11 implementations. The demand for better medium efficiency and a versatile QoS platform, however, increased interest in this optional access mechanism of the 802.11 MAC.
The hybrid nature of the 802.11 MAC has caused proposals to focus either on the DCF or the PCF. However, by only looking at the PCF and not considering the DCF overlooks the fact that the 802.11 MAC always spends some time under the DCF access mechanism rules and that the DCF is also an integral part of a PCF based system. The system always has to spend at least a small part of its time under the DCF. The PCF has the fundamental characteristic that a station can't access the medium unless explicitly polled. However, to be polled, the station must first make itself known to the Point Coordinator, which requires medium access. Therefore, a PCF based solution must support both contention-free and contention periods. A contention period is required for bursty traffic, adjacent BSSes, probe requests, association and re-association requests, etc.
FIG. 1 shows an example of a sample rate for a real-time application in a WSTA and the associated polling sequences for that WSTA. The lower portion 12 of FIG. 1 shows the WSTA sample rate. The upper graph 14 shows the polling sequences. The polling sequence starts with a DTIM beacon 16. The contention-free period 18 starts immediately after the DTIM beacon 16. During the contention-free period 18, the point controller initiates polling sequences 20. After the polling sequences 20 is shown an idle time period 22. The idle time period 22 is then followed by an additional polling sequences 20 and idle time periods 22. Following the contention-free period 18 is the contention period 24. After the contention period 24, another DTIM beacon 16 starts a new sequence of a contention-free period 18 and a contention period 24.
In FIG. 1, the DTIM beacon rate is slower than the sampling rate. Idle time 22 is introduced if the CFP is extended so that the same WSTA can be polled more than once per CFP. Latency is introduced if the channel is overloaded in the contention period.
Delay sensitive applications, such as VoIP, require short DTIM intervals (i.e. 30 milliseconds) to minimize CF polling latency. A fast DTIM beacon rate wastes bandwidth because of the beaconing overhead and because contention-based transmissions cannot span the TBTT (per the baseline proposal). A fast DTIM beacon rate also requires power-save WSTAs to wake up more often, for example to receive multicast frames and buffered unicast frames.
In installations with multiple QoS applications with different service rates, the DTIM beacon rate cannot match the sampling rate for each application. Actually, it is difficult to match the sampling rate for any application. It is not efficient to arbitrarily poll WSTAs in every CFP. Therefore, some sort of signaling protocol is necessary to suppress unnecessary polls. In addition, a need exists for a protocol that can divorce the service rate, for active parameterised stations from the beacon rate. Periodic polling is not optimal for intermittent traffic. VoIP traffic can be intermittent due to silence suppression.
Depending on the ‘load of the medium’, the system may spend more or less time in the CFP. In a heavily loaded system, the system may spend the larger part in the CFP while a mildly loaded system may spend the larger part in the CP. The balance between the two access mechanisms is a function of the medium load. As a consequence, both access mechanisms must provide the same QoS capabilities. The transition between one access mechanism and the other must be a smooth one. This is especially a challenge in average loaded systems where the DCF efficiency is starting to breakdown while the PCF efficiency is not yet optimal. For the upper layer protocol (or application) the performance profile of the service should be linear over all medium conditions and this is something that should be considered when proposing a PCF based system. Therefore, when proposing PCF enhancements, one also to consider the interaction between the PCF and the DCF and the dynamics of the system as a whole under various medium load conditions.
PCF combines the ability of full medium control with optimal medium efficiency, without suffering from scalability problems. However, there are two issues that limit the use of the current PCF for QoS systems. Section 9.3.4 and specifically clause 9.3.4.1 of the IEEE 802.11 standard imposes strict rules upon the order in which stations are addressed or polled. This is undesirable in a QoS system. Secondly, there is no mechanism, other than the More-Data bit, that allows a station to communicate its queue states to the PC.
The entity in the PC that actually calculates the order in which stations are addressed is in literature often referred to as the ‘scheduler’. The rules for the handling of the polling list limit the freedom of the scheduler and may conflict with QoS requirements. The original intent to poll stations in order of ascending AID value is not clear from the standard and in fact the whole concept of a polling list may become obsolete due to the introduction of a mechanism for communicating To-DS queue state(s). Therefore, the rules as defined in section 9.3.4 are neglected for this method.
In order to make accurate scheduling decisions, the scheduler in the PC needs to have knowledge about the queues in the associated stations. The More-Data bit is a Boolean that could be used for this but only allows communication of a truth-value on the queue state; for a good scheduler implementation this is not enough. Preferably, the scheduler needs to know the length and priority of the next frame in the queue of each station.
Scheduling problems arise with CFPs in networks with overlapping BSSes in the same ESS or multiple ESSes. A CFP is not completely contention-free unless all stations in any neighboring BSS, that are in range of any active stations in the BSS, set their NAV for CFPMaxDuration for the CFP. Therefore, the total “reservation area” for a CFP can be very large compared to the coverage area of the point controller for the BSS.
The baseline proposal defines a “proxy beacon” mechanism where WSTAs in a BSS repeat AP beacons to extend the area for propagating beacon information to hidden nodes. The baseline proposal does not define which WSTAs should send proxy beacons and it does not define the scheduling mechanism for proxy beacons. Also, it is not clear whether a hidden node in a neighboring BSS, that receives proxy CFP beacons, should set its NAV for CFPMaxDuration for the TBTT of the associated hidden CFP. If hidden nodes do not set their NAV for proxy beacons, then CFPs are not contention-free.
If hidden nodes set their NAV for CFPMaxDuration for a hidden CFP (due to proxy beacons or some other mechanism) then two difficult problems must be considered. First, as noted above, spatial reuse is severely inhibited as compared to DCF. The baseline proposal attempts to solve the “spatial reuse” problem by classifying WSTAs as belonging to overlap and non-overlap sets per BSS. However, that approach does not work for all applications because it assumes that a WSTA is relatively stable compared to its transmission rate and it uses the flow error rate as an overlap indicator. Second, if a hidden CFP ends early, then bandwidth is wasted because hidden nodes may not be able to determine that the hidden CFP has ended. It has been suggested that WSTAs that transmit proxy beacons could also transmit “proxy CF-End” messages or CF-End messages could be transmitted on the distribution system. The first solution is “chatty” and the second solution is not generally applicable because the distribution system may introduce latency (i.e. if it includes wireless links or IP tunnel links).
It should also be noted that in the PCF/CFP model, where the NAV is set for long CFPs, use of sophisticated techniques that increase spatial reuse by varying the transmit power and/or antenna direction per unicast transmission sequence is inhibited.
One suggested PCF enhancement that can ease the overlapping BSS problem and alleviate the scheduling problem is the Contention Free Burst. A paper entitled “Suggested 802.11 PCF Enhancements and Contention Free Bursts”, IEEE 802.11-00/113 (May 10, 2000), written by Maarten Hoeben and Menzo Wentink, hereby incorporated by reference, describes bi-directional contention-free bursts that include point controller polling.
The Contention Free Bursts concept breaks up a Contention Free Period into smaller Contention Free Bursts. This is useful for two reasons: First, it allows the PC to relinquish medium control to other BSSs in the same area. Second, in the case of average loaded systems, the PC can temporarily give-up medium control (to possibly another BSS) and defer control until new frames are available for transmission.
Normally, a CFP starts with the transmission of a Beacon. A SIFS after the Beacon, the first CFB is started. Within the CFB, the PCF transfer procedures apply as defined in section 9.3.3 of the IEEE 802.11 standard. CFBs have a maximum duration of CFBMaxDuration. The duration remaining in the CFB is encoded in the Duration/ID field of every From-DS frame sent by the PC. The CFB may be foreshortened but never lasts longer than CFBMaxDuration. The end of a CFB is signaled through a duration of 0.
Between two CFBs the PC performs a random backoff, selected from a range of 0 to CW-1 slots. The random backoff mechanism allows PCs to contend for the medium to start a new CFB. In the current definition of the CFP, all stations (including other access points) set their NAV based on the Duration Remaining field in the CF-Parameter set and reset the NAV upon receiving a CF-End. This prevents access points and stations from accessing the medium during observed medium idleness during the CFP (possibly caused by the transmission of a frame by a hidden node). PCs may use the backoff mechanism to contend for the medium and start a CFP or continue their own CFP with a new CFB. In a sense the CFB concept works like a superimposed DCF over the PCF. PCs coordinate their bursts by using the backoff-mechanism, deferring and restarting the backoffs whenever a PC starts a CFB or ends the CFB. The CFBs are protected through the NAV-alike duration field in the redefined in Duration/ID field, CPs use the information as received in the ToDS frames from other CPs to update their CF-Nav and defer backoff and start of a new CFB.
Note that only PCs contend for medium control; stations (and legacy access points) do not attempt to access the medium during the periods of medium silence caused by the backoff periods because they adhere to the Contention Free Periods of (at least one of) the BSSs. A CFB is furthermore protected from interference of legacy implementations due to the SIFS/PIFS interframe spaces, and a Duration/ID field that is interpreted as a very long NAV.
Another concern is that PCF and DCF applications do not always coexist well. The PCF model only supports “polled” inbound transmissions during a CFP. As a result long PCF-based CFPs can starve DCF-based stations. The problem is exacerbated when CFPs in overlapping BSSes must be scheduled to avoid CFP contention. PCF polling is appropriate for isochronous applications, but DCF is more appropriate for asynchronous data. It should not be assumed that PCF polling is used for all high-priorty inbound transmissions; however, the current baseline model inherently prioritizes PCF over DCF. As an example, consider inbound asynchronous high-priority network control transmissions. Such transmissions can be delayed extensively by lower priority PCF transmissions.
The current 802.11 standard specifies that an AP must buffer all outbound multicast frames and deliver them immediately following a DTIM beacon if “strict ordering” is not enabled, then. Therefore, short DTIM intervals are necessary to support multicast applications that cannot tolerate delays. In addition, outbound multicast transmissions are more susceptible to problems associated with inter-BSS contention and hidden nodes because multicast frames are not retransmitted (i.e. after a collision with a hidden node) and the DCF channel reservation mechanisms cannot be used for multicast frames.
The baseline proposal removes the restriction that buffered multicast/broadcast frames must be sent immediately following a DTIM beacon. The baseline proposal requires that QoS WSTAs must respond to +CF-Polls. Therefore, it is strongly recommended that QoS stations should also associate as CF-Pollable (i.e. not requesting to be polled). If QoS power-save WSTAs do not use the PS-Poll mechanism for the delivery of outbound buffered messages, an AP can more easily schedule outbound transmissions for PS WSTAs. Note that CF-Pollable stations do not send PS-Poll frames to solicit outbound transmissions. Instead, a CF-Pollable station must stay awake, after it receives a DTIM beacon with its AID bit set on, until either it receives a unicast frame with the more bit set off, or a TIM with its AID bit set off. Therefore, it is generally assumed, but not required, that QoS WSTAs with active flows will operate in active mode because a point controller cannot successfully poll a WSTA that is in power-save mode.
The baseline proposal defines “awake-time epochs” that can, optionally, be used to set an awake-time window for periodic polling and/or outbound data transmissions. However, awake-time epochs introduce complexity for P-CFB polling and PCF polling. If power management must be supported, it would be simpler to schedule P-CFB polls for power-save parameterised WSTAs, if such WSTAs used automatic power-save intervals. Such a power-save WSTA can remain in power-save mode for, at most, the duration of its “automatic power-save interval”, following an inbound transmission, where the duration is selected to match the WSTAs inbound transmission rate. The point controller can simply adjust the duration of the poll timer, for a WSTA, so that it is greater than the sleep-time window duration. The point controller can then poll a WSTA and/or deliver outbound buffered data for a WSTA when the poll timer expires.
Therefore, for the reasons set forth above, there is a need for a contention-based channel access method for supporting parameterised QoS applications. Furthermore, the channel access method must coexist well with PCF and DCF applications.